import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ws
 * Date: 2023-03-21
 * Time: 16:43
 */

//https://leetcode.cn/problems/reverse-words-in-a-string/description/
public class Main2 {
    public String reverseWords(String s) {
        //取出前导和后导的空格,调整单词间的空格数量
        StringBuilder sb = trimSpace(s);
        //反转整个字符串
        reverse(sb, 0, sb.length() - 1);
        //反转每个单词
        reverseEachWord(sb);
        return sb.toString();
    }

    public StringBuilder trimSpace(String s) {
        int left = 0;
        int right = s.length() - 1;
        //前导空格
        while (left <= right && s.charAt(left) == ' ') {
            left++;
        }
        //后导空格
        while (left <= right && s.charAt(right) == ' ') {
            right--;
        }
        //去除单词间多余的空格
        final StringBuilder sb = new StringBuilder();
        while (left <= right) {
            char c = s.charAt(left);
            if (c != ' ') {//将非空格拼接
                sb.append(c);
            } else if (sb.charAt(sb.length() - 1) != ' '){//保证每个单词的尾部只有一个空格
                sb.append(c);
            }
            left++;
        }
        return sb;
    }

    public static void reverse(StringBuilder sb, int left, int right) {
        while (left < right) {
            char temp = sb.charAt(left);
            sb.setCharAt(left++, sb.charAt(right));
            sb.setCharAt(right--, temp);
        }
    }
    public void reverseEachWord(StringBuilder sb) {
        int n = sb.length();
        int start = 0;
        int end = 0;
        while (start < n) {
            //每次循环到单词的结尾
            while (end < n && sb.charAt(end) != ' ') {
                end++;
            }
            //反转单词
            reverse(sb, start, end - 1);
            //更新start
            start = end + 1;
            //更新end，避免一直循环
            end++;
        }
    }

}


//import java.util.Scanner;
//        import java.util.Arrays;
//
//public class Main{
//    public static void main(String[] args){
//        Scanner sc=new Scanner(System.in);
//        String in=sc.nextLine();
//        String[] ins=in.split(" ");
//        StringBuilder builder=new StringBuilder();
//        for(int i=ins.length-1;i>=0;i--){
//            builder.append(ins[i]+" ");
//        }
//        builder.deleteCharAt(builder.length()-1);
//        System.out.print(builder.toString());
//    }
//}

//class Solution {
//    public String reverseWords(String s) {
//        //去除前后的空格
//        s = s.trim();
//        //正则表达式分割单词字符
//        List<String> wordList = Arrays.asList(s.split("\\s+"));//匹配任意空白字符
//        Collections.reverse(wordList);//倒置list
//        return String.join(" ", wordList);//返回新的string，并包含分隔符
//    }
//}


//class Solution {
//    public String reverseWords(String s) {
//        s = s.trim();
//        String[] strs = s.split("\\s+");
//        StringBuilder sb = new StringBuilder();
//        for (int i = strs.length - 1; i >= 0; i--) {
//            sb.append(strs[i] + " ");
//        }
//        sb.deleteCharAt(sb.length() - 1);
//        return sb.toString();
//    }
//}

//class Solution {
//    public String reverseWords(String s) {
//        int left = 0;
//        int right = s.length() - 1;
//        while (left <= right && s.charAt(left) == ' ') {
//            left++;
//        }
//        while (left <= right && s.charAt(right) == ' ') {
//            right--;
//        }
//        //利用栈的性质
//        Deque<String> stack = new LinkedList<>();
//        StringBuilder sb = new StringBuilder();
//        while (left <= right) {
//            char c = s.charAt(left);
//            if (sb.length() != 0 && c == ' ') {
//                //将单词
//                stack.push(sb.toString());
//                //清空sb
//                sb.setLength(0);
//            } else if (c != ' ') {
//                sb.append(c);
//            }
//            left++;
//        }
//        //最后一个单词没有空格，需要手动添加
//        stack.push(sb.toString());
//        return String.join(" ", stack);
//    }
//}